package ua.yandex.collections;

import java.util.Comparator;

public class MyCollections {

    /**
     * Reverses the order of the elements in the specified list
     */
    public static void reverse(MyList list) {
        Object[] elements = list.toArray();
        int length = elements.length;

        for (int i = 0; i < length / 2; i++) {
            swap(elements, i, length - i - 1);
        }

        list.clear();
        list.addAll(elements);
    }

    private static void swap(Object[] elements, int i, int j) {
        Object tmp = elements[i];
        elements[i] = elements[j];
        elements[j] = tmp;
    }

    /**
     * Реализует рекурсивный поиск в отсортированном массиве методом бисекции.
     */
    public static int binarySearch(MyList list, Object key) {
        return binarySearch(list, key, new Comparator() {

            @Override
            public int compare(Object first, Object second) {
                return ((Comparable) first).compareTo(second);
            }

        });
    }

    //Реализует рекурсивный поиск в отсортированном массиве методом бисекции.
    public static int binarySearch(MyList list, Object key, Comparator cp) {
        if (list instanceof MyArrayList) {
            return indexedBinarySearch(list, key, cp);
        } else {
            return sequentialBinarySearch(list, key, cp);
        }
    }

    private static int indexedBinarySearch(MyList list,
                                           Object key,
                                           Comparator cp) {
        int lo = 0;
        int hi = list.size() - 1;

        while (lo <= hi) {
            int middle = lo + (hi - lo) / 2;
            int cmp = cp.compare(key, list.get(middle));

            if (cmp == 0) {
                return middle;
            } else if (cmp < 0) {
                hi = middle - 1;
            } else {
                lo = middle + 1;
            }
        }

        return -lo - 1;
    }

    private static int sequentialBinarySearch(MyList list,
                                              Object key,
                                              Comparator cp) {
        MyArrayList arrayList = new MyArrayList();
        arrayList.addAll(list.toArray());

        return binarySearch(arrayList, key, cp);
    }

}
